package com.shindo.novie.class04;

/**
 * 单链表，K个节点的组内逆序调整
 * 给定一个单链表的头节点head，和一个正数k
 * 实现k个节点的小组内部逆序，如果最后一组不够k个就不调整
 * 例子：
 * 调整前：1-->2-->3-->4-->5-->6-->7-->8, k = 3
 * 调整后：3-->2-->1-->6-->5-->4-->7-->8
 * <p>
 * 测试链接：https://leetcode.com/problems/reverse-nodes-in-k-group/
 * 总结：
 * 注意边界值处理，同时需要及时调整各个小组反转后的连接
 */
public class Code04_ReverseNodesInKGroup {
    public static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int value) {
            val = value;
        }

        public ListNode(int value, ListNode next) {
            this.val = value;
            this.next = next;
        }
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode start = head;
        ListNode end = getKGroupEnd(start, k);
        if (end == null) {
            return head;
        }
        //第一组凑齐了，且第一组反转后的头节点也是整个链表的头节点
        head = end;
        reverse(start, end);
        //上一组的结尾节点
        ListNode lastEnd = start;
        //判断分组后的元素是否为null,为null则停止操作
        while (lastEnd.next != null) {
            start = lastEnd.next;
            end = getKGroupEnd(start, k);
            if (end == null) {
                return head;
            }
            reverse(start, end);
            //调整上一组的尾节点 衔接 上下一组反转后的头节点
            lastEnd.next = end;
            //上一组的尾节点，调整为这一组反转后的尾节点
            lastEnd = start;
        }
        return head;
    }

    /**
     * 获取组内k个节点的尾节点
     */
    public static ListNode getKGroupEnd(ListNode start, int k) {
        while (--k != 0 && start != null) {
            start = start.next;
        }
        return start;
    }

    /**
     * 小组内单链表反转
     */
    public static void reverse(ListNode start, ListNode end) {
        //记录下一组的头节点
        end = end.next;
        ListNode pre = null;
        ListNode cur = start;
        ListNode next = null;
        //判断当前节点是否已经移动到下一组的头节点做为结束判断
        while (cur != end) {
            //单项链表的反转
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        //把反转后的尾节点连接上 下一组的头节点
        start.next = end;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6, new ListNode(7, new ListNode(8)))))));
        head = reverseKGroup(head, 3);
        while (head != null) {
            System.out.println(head.val);
            head = head.next;
        }

    }
}
